/*
 * @Author: w
 * @Date: 2022-02-21 22:54:01
 * @Description: 剑指 Offer 53 - I. 在排序数组中查找数字 I
 */

// 排序数组，二分查找（mid)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

// 遍历
// 没有用到排序数组条件
var search = function (nums, target) {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] == target) count++;
  }
  return count;
};

// 二分查找
// 最重要的中位数没有实现
var search = function (nums, target) {
  let count = 0,
    left = 0,
    right = nums.length - 1;
  while (left <= right) {
    if (nums[left] == target) {
      count++;
    }
    if (nums[right] == target && left != right) {
      count++;
    }
    left++;
    right--;
  }
  return count;
};

// 二分查找
const binarySearch = (nums, target, lower) => {
  let left = 0,
    right = nums.length - 1,
    ans = nums.length;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > target || (lower && nums[mid] >= target)) {
      right = mid - 1;
      ans = mid;
    } else {
      left = mid + 1;
    }
  }
  return ans;
};

var search = function (nums, target) {
  let ans = 0;
  const leftIdx = binarySearch(nums, target, true);
  const rightIdx = binarySearch(nums, target, false) - 1;
  if (
    leftIdx <= rightIdx &&
    rightIdx < nums.length &&
    nums[leftIdx] === target &&
    nums[rightIdx] === target
  ) {
    ans = rightIdx - leftIdx + 1;
  }
  return ans;
};

// indexOf、lastIndexOf
var search = function (nums, target) {
  const leftIdx = nums.indexOf(target);
  const rightIdx = nums.lastIndexOf(target);
  return rightIdx - leftIdx + 1;
};
